The present invention relates to an apparatus and a method for maximizing the quality of a color image at a given color resolution and more particularly relates to reproducing a high quality color image using a lower color resolution.
To accurately represent a color image using digital electronics, the image is quantized to discrete locations and colors. Typically, the image is divided into a two-dimensional grid of uniformly shaped boxes, and each box is assigned a single color. This allows a computer system to represent a color image internally as a two-dimensional array of digital color values. Images represented in this manner are known as bitmapped images. A typical color imaging standard currently in use (the VGA standard), represents a color image with a 640xc3x97480 array of 4-bit color values. Such an array of color values can be easily stored by the computer system in a memory device. Also with this form of color image representation, the computer system can easily reproduce the stored image using a color monitor or printer with an array of colored dots (commonly referred to as pixels).
In a typical computer system, color is quantized according to the red-green-blue (RGB) color model. According to the RGB model, colors are specified by an ordered triple of values corresponding to the intensities of red, green, and blue light that are mixed to form the color. (Red, green and blue light are considered to be additive primaries.) Each of the intensity values varies from zero to one, with a one indicating full intensity of the color. For example, the ordered triple, (1,0,1), refers to the color magenta formed by the mixture of full intensity red with full intensity blue. The RGB color model is directly applicable to color monitors wherein an electron gun is used to excite red, green and blue phosphors on a screen to varying intensities. The range of colors that are displayable on such a device is known as the color gamut of the device. Other color quantization models are also commonly used and may be more suitable to some applications. However, in general, all color models use a three dimensional representation of the color gamut.
At times, colors are specified even more abstractly in a computer system using a single number or color value instead of an ordered triple in order to minimize the space required to store an image. Usually, the computer system maintains a look-up table to associate these color values with their corresponding RGB (or other color model) ordered triple. The colors in the table make up a set of colors that can be simultaneously used in a single image. The set of colors that can be simultaneously used in an image is known as the color palette.
The perceived quality of the digitized color image when reproduced depends upon its spatial and color resolutions. The spatial resolution of an image is related to the number and size of the boxes (or pixels when reproduced) into which the image is divided (and hence related to the size of the array used to represent the image). The color resolution of an image is related to the number of discrete colors that can be simultaneously used in the image (i.e., the size of the color palette). The greater the spatial and color resolutions of an image, the better its quality. For example, an image displayed with a spatial resolution of 1024xc3x97768 pixels is of perceptibly higher quality than the same sized image displayed with a spatial resolution of 640xc3x97480 pixels. Also, when displayed, an image where each color is represented by an 8-bit value (allowing the use of up to 256 different colors in the same image) is of perceptibly higher quality than an image where each color is represented by a 4-bit value (16 different simultaneous colors).
Current high end computer systems represent color images with 24-bit color values (16.8 million colors) and provide a spatial resolution of 1280xc3x971024 or higher. Systems with 24-bit color resolution are considered to be xe2x80x9ctrue colorxe2x80x9d systems since the color at any pixel in the digitized image is specified with adequate color resolution to be indistinguishable from its actual color in the original image. These systems are therefore capable of reproducing images with astonishing tonal accuracy and crispness.
There are situations, however, when it is desirable to reproduce an image that has been digitized at a certain color resolution (24-bit true color, for example) using a lower color resolution. For example, it may be desirable to display with pre-existing VGA or super VGA standard hardware a color image digitized at a higher color resolution. It may also be desirable to design less expensive hardware than that required for 24-bit color resolution while providing a similar image quality. This problem can be restated generally as that of achieving the best quality color image with a limited color resolution.
In the prior art, two different approaches have been taken to solving the problem of optimizing the quality of a high resolution image reproduced at a low color resolution. The first approach involves optimally choosing the set of colors for the color palette. In typical computer systems, the color palette is user selectable, not fixed. Thus, in a VGA standard (4-bit color resolution) system, some or all of the palette of 16 colors can be designated by the user. The quality of a reproduced image can be greatly enhanced by properly selecting the optimal color palette.
Some prior art systems use adaptive techniques aimed at choosing colors for a palette that are optimal for the particular image being reproduced. One such technique is known as the popularity algorithm. This technique chooses as colors for a palette, those colors which occur most frequently in the image being reproduced. For example, for 8-bit color resolution reproductions, the 256 colors used most frequently in the image are chosen to fill, the color palette. Then, when the image is reproduced, each color in the image is mapped to the nearest color in the palette. Usually, the quality of the resulting image is greatly enhanced since the actual colors of most of the image""s pixels will be in the palette.
Such adaptive palette techniques, however, produce undesirable effects in a windowing environment in which several images may be simultaneously displayed. Adapting the color palette to an individual image on the display typically degrades the quality of the remaining images. Also, when the focus of the windowing environment is subsequently changed to another individual image on the display, the color palette must be re-adapted to that image. Consequently, the quality of the image to which the color palette was previously adapted becomes degraded. This undesirable effect is known as a palette war.
A second approach relies on the eye""s ability to blend the colors of adjacent pixels so that an intermediate color is perceived. This approach focuses on how the pixel colors are mapped to colors in the palette to best approximate the pixel color when viewed by the human eye. (The process of mapping pixel colors to palette colors is also referred to herein as xe2x80x9crenderingxe2x80x9d a pixel color.)
In a standard mapping of pixel colors to palette colors, the pixel colors are simply mapped to the nearest palette color. (The nearness of two colors is determined by the distance separating the colors in the RGB or other color model.) The result is that all pixels in an area of uniform color are mapped to the same palette color. Although the pixel color is mapped to the nearest palette color, there may be a significant difference or error between the pixel color and the mapped palette color. This difference can often be readily perceptible to a viewer.
Better results can be obtained with mapping techniques that alternately map a pixel color to two or more of the nearest palette colors such that the average error between the pixel color and the palette colors is zero. When pixels are mapped in this fashion, the eye blends or averages the palette colors of several neighboring rendered pixels in the reproduced image to perceive an approximation of the original pixel colors. Two techniques that use this approach are ordered dithering and error diffusion. These techniques are both generally referred to as dithering processes.
With the ordered dithering technique, a uniform grid of colors is used as a palette (i.e. the colors of the palette are uniformly spaced in each of the red, green and blue dimensions). A pixel""s color is mapped by adding an amount of dither to each dimension of the color""s corresponding RGB ordered triple and then truncating the result to a palette color. The amount of dither added is dependent on the position (in cartesian coordinates) of the pixel in the image. The pixel""s cartesian coordinate is used to locate a scaling factor in a square (nxc3x97n) threshold matrix. For a pixel with the cartesian coordinate (x,y) the scaling factor located at the position (x mod n, y mod n) in the threshold matrix is used. To determine the amount of dither added in each dimension of the color model, the scaling factor is multiplied by the spacing between palette colors in that dimension. By determining the amount of dither with a threshold matrix rather than randomly, the amount of dither varies in a recuring pattern across the image. This produces an appearance of uniform color in those areas of an image originally uniformly colored. The following is a typical threshold matrix.   "AutoLeftMatch"                    0                              6          16                                      9          16                                      15          16                                              11          16                                      13          16                                      2          16                                      4          16                                              7          16                                      1          16                                      14          16                                      8          16                                              12          16                                      10          16                                      5          16                                      3          16                    
With error diffusion, the color of each pixel is not mapped independently of its neighboring pixels to palette colors. When error diffusing, the color of the pixels in the image are mapped one-by-one straightforwardly to the nearest palette color. However, as each pixel is mapped, the error (or directed distance in the color model) between the actual pixel color and the palette color to which it is mapped is calculated. This error is diffuse to those neighboring pixels which have not yet been mapped. A common method for diffusing the error is know as the Floyd-Steinberg filter, represented by the following matrix (which assumes the pixels are mapped from left to right and top to bottom).   "AutoLeftMatch"                    0                    0                    0                            0                    CURRENTPIXEL                              7          16                                              3          16                                      5          16                                      1          16                    
According to the Floyd-Steinberg filter, {fraction (7/16)} of the error is added to the pixel to the right of the pixel being mapped, {fraction (5/16)} to the pixel below, {fraction (3/16)} to the pixel below and left, and {fraction (1/16)} to the pixel below and right. Other commonly used error diffusion filters include the Stucki filter and the Burkes filter.
One problem with both the ordered dithering and error diffusion techniques is that discernable artifacts are often produced in the image. Thus, while the standard ordered dithering and error diffusion techniques serve to improve the color quality of the image, the resulting image is generally flawed. The object of the present invention therefore is to reproduce color images using a lower color resolution while maintaining a high color quality. A further object is to reproduce color images with minimal artifacts.
The present invention maximizes the color quality of images reproduced at lower color resolutions by using a single, carefully designed color palette. To avoid palette wars and the additional computational overhead associated with adaptive palette methods, the present invention utilizes the same palette in the reproduction of all images. This universal palette is structured according to the sensitivities of the human eye to maximize the quality of reproduced images with a minimum color resolution.
The human eye is actually more sensitive to the luminance of light than to its color, and is particularly able to distinguish differences in luminance at low luminances of light. Color can therefore be more efficiently encoded by emphasizing luminance over color and by concentrating palette colors in the regions of the color model having a lower luminance.
In order to emphasize luminance over color, the colors of the palette are chosen by first selecting a plurality of levels of uniform luminance in the color model and then selecting the palette colors from those luminance levels. The palette colors are thus grouped into levels of uniform luminance. With this structure, luminance can be emphasized over color when mapping pixels by mapping pixel colors to the nearest of the palette colors on an adjacent luminance level even when a palette color on a non-adjacent luminance level would be closer in color.
The palette colors are concentrated towards lower luminances by spacing the luminance levels closer together near black in the color model and farther apart near white. (In the RGB model, black is formed when red, green and blue primaries are at their minimum intensity and white is formed when the primaries are all at their maximum intensities.) In one embodiment of the invention, the spacing between luminance levels increases from black to white according to a cubic function.
The human eye is also more sensitive to some colors of light than others. The custom palette can therefore be further structured according to these sensitivities to provide more efficient color encoding. For example, when an image is reproduced using dithering techniques (e.g., ordered dithering and error diffusion) intended to render non-palette colors using patterns of two or more palette colors, the eye may be unable to effectively blend the colors in the pattern if it is particularly sensitive to the difference between those colors. Instead of sensing the intended non-palette color, the eye perceives the color pattern itself. When such patterns are perceptible to the eye, they are known as mapping or rendering artifacts.
One particular sensitivity of the human eye is its greater sensitivity to colors of low saturation (e.g., pastels). In other words, the eye is better capable of discerning a difference between colors with low saturation than between colors of high saturation. Since the eye is very sensitive to the difference between low saturation colors, the rendering of a low saturation color with a pattern comprising a gray and a high saturation color should be avoided. The eye will instead perceive the pattern itself (an artifact). Also, the rendering of a gray color using a patten of two highly saturated colors should be avoided. The perceptible artifacts resulting from such renderings are referred to herein as the Saruman effect.
In the present invention, the Saruman effect is avoided by structuring the palette to include the gray color on each of the luminance levels, and a circle of additional colors on each luminance level around the gray color. The number of additional colors encircling the gray on each level is related to the area of the luminance level within the color model. On luminance levels having larger areas, the additional colors can be grouped in two or more circles. By including the gray color of each luminance level, it is never necessary to render gray colors or very lowly saturated colors with a pattern of more highly saturated colors. Also, by including a number of additional colors in a circle around the gray color on each luminance level, it is not necessary to render a color of low saturation using a gray and a fully saturated color. Instead, two or more of the additional colors, which have a low saturation, can be used.
A further problem results from attempting to render a color near the boundary of the color model (a highly saturated color) by averaging colors near the center of the color model (colors of lower saturation). Actually, it is impossible to render highly saturated colors in this manner. In order to render a pixel color by blending a pattern of other colors with the eye, the blended colors must surround (or be located on opposite sides of) the pixel color in the color model. Thus, when the pixel color lies on or near a boundary of the color model, it can only be rendered using a pattern which includes at least one color on the boundary of the color model.
To guarantee that all colors in the color model can be rendered, the palette must include at least the colors at the vertices of the color model. Pixel colors on a boundary of the color model can then be rendered using the colors at the vertices of the color model that lie on each side of that pixel color. However, since in the present invention, pixel colors are mapped to palette colors from only those luminance levels adjacent the pixel color, the palette should include the colors at the vertices of at least every other luminance level. Boundary colors can then be rendered by mapping to colors at the vertices of one of the adjacent luminance levels.
The eye is also more sensitive to changes in the intensity of the green component of colors than to changes in the intensity of the red component, and more sensitive to changes in the intensity of the red component than the blue component. Further, the eye is particularly sensitive to artifacts on images of the human face and in large areas of constant color or smooth gradations of color. To prevent discernable artifacts from appearing when rendering these types of colors, the palette colors are chosen to be more concentrated in those regions of the color model where the eye is most sensitive. For example, the palette colors will be chosen to be more highly concentrated in the flesh colors, and sky colors. Also, the palette colors can be chosen to be more closely spaced in the green dimension and further apart in the blue dimension.
The present invention also includes an improved rendering method. One feature of the improved rendering method is a luminance emphasized mapping method. As described above, due to the eye""s greater sensitivity to luminance than to color, better results can be obtained by emphasizing luminance over color when mapping pixel colors to the palette. Using a palette which is structured to have palette colors grouped on discrete levels of uniform luminance (such as the palette described above), luminance is given greater emphasis by mapping each pixel""s color to the nearest palette color on the luminance levels adjacent to the pixel color. Such mapping ensures that each pixel is mapped to a palette color of nearly equal luminance even if a palette color varying more in luminance from the pixel color would be closer in color.
Another feature of the rendering method is a mapping method for preventing an effect referred to herein as the anti-Saruman effect. The anti-Saruman effect occurs when a color being rendered is highly saturated and the nearest neighboring color in the palette is of low saturation. If the color is rendered using the nearest neighbor, low saturation palette color, a loss in saturation results that cannot be recovered even if the color is also rendered using other highly saturated colors through error diffusion. The anti-Saruman effect can be prevented by preventing mappings of highly saturated colors to low saturation palette colors. In a preferred embodiment of the present invention, mappings of a highly saturated color to a low saturation color are prohibited if the error of the highly saturated color from the low saturation color, when doubled, would be outside the color gamut of the RGB color model. The highly saturated color is instead mapped to the nearest palette color not violating this rule.
In a preferred embodiment of the invention, the above described mapping methods are utilized as part of an error diffusion process. In accordance with the error diffusion process, the color of a pixel, as modified by error diffused from previously rendered pixels, is mapped to a palette color using the mapping methods. The error or distance in the color model of the palette color from the unmodified pixel color is then calculated. Finally, the error is diffused to not yet rendered neighboring pixels.
Since the rendering method of the invention can be quite computationally intensive, reproduction of an image using this method can be sped up considerably by pre-determining the mapping of each possible pixel color and storing the results in look-up table form. Images can thereafter be reproduced by simply looking up the mapping of each pixel""s color in the table rather than having to calculate the mapping of each pixel as the image is reproduced. However, for an image in which pixel colors are encoded using a high color resolution, such a table may be prohibitively large for most applications. For example, for images where pixel colors are encoded as 24-bit values, such a table would require nearly 16.8 million entries. In the present invention, the table size is reduced through the use of an intermediate palette which has a color resolution intermediate to those of the original image and the custom palette. The mapping of each color in the intermediate palette is stored in a look-up table. Since the number of colors in the intermediate palette is less than the number of possible colors in the image, a much smaller sized look-up table is required. Pixel colors are mapped to the custom palette by first dithering the pixel colors to intermediate palette colors using an ordered dithering method. The mapping of the pixel colors to the custom palette are then determined by looking up the intermediate palette color in the table.
The size of the look-up table can be further minimized without significantly degrading the quality of the reproduced image by also structuring the intermediate palette according to the eye""s greater sensitivity to some colors. For example, in accordance with eye""s greater sensitivity to changes in the intensity of the green component of colors and lesser sensitivity to changes in the intensity of their blue component, the colors of the intermediate palette are spaced closest together in the green dimension and furthest apart in the blue dimension. More specifically, in the preferred embodiment of the invention, the intermediate palette is structured as a uniform grid of colors with more levels of green than of red, and fewer levels of blue.
Additional features and advantages of the invention will be made apparent from the following detailed description of a preferred embodiment which proceeds with reference to the accompanying drawings.